package com.sheng.leetcode.year2023.month12.day26;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/12/26
 * <p>
 * 1349. 参加考试的最大学生数<p>
 * <p>
 * 给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），<p>
 * 就用 '#' 表示；否则，用 '.' 表示。<p>
 * 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，<p>
 * 但是看不到直接坐在他前面或者后面的学生的答卷。<p>
 * 请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。<p>
 * 学生必须坐在状况良好的座位上。<p>
 * <p>
 * 示例 1：<p>
 * 输入：seats = [["#",".","#","#",".","#"],<p>
 * [".","#","#","#","#","."],<p>
 * ["#",".","#","#",".","#"]]<p>
 * 输出：4<p>
 * 解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。<p>
 * <p>
 * 示例 2：<p>
 * 输入：seats = [[".","#"],<p>
 * ["#","#"],<p>
 * ["#","."],<p>
 * ["#","#"],<p>
 * [".","#"]]<p>
 * 输出：3<p>
 * 解释：让所有学生坐在可用的座位上。<p>
 * <p>
 * 示例 3：<p>
 * 输入：seats = [["#",".",".",".","#"],<p>
 * [".","#",".","#","."],<p>
 * [".",".","#",".","."],<p>
 * [".","#",".","#","."],<p>
 * ["#",".",".",".","#"]]<p>
 * 输出：10<p>
 * 解释：让学生坐在第 1、3 和 5 列的可用座位上。<p>
 * <p>
 * 提示：<p>
 * seats 只包含字符 '.' 和'#'<p>
 * m == seats.length<p>
 * n == seats[i].length<p>
 * 1 <= m <= 8<p>
 * 1 <= n <= 8<p>
 */
public class LeetCode1349 {

    @Test
    public void test01() {
        char[][] seats = {
                {'#', '.', '#', '#', '.', '#'},
                {'.', '#', '#', '#', '#', '.'},
                {'#', '.', '#', '#', '.', '#'}};
//        char[][] seats = {
//                {'.', '#'},
//                {'#', '#'},
//                {'#', '.'},
//                {'#', '#'},
//                {'.', '#'}};
//        char[][] seats = {
//                {'#', '.', '.', '.', '#'},
//                {'.', '#', '.', '#', '.'},
//                {'.', '.', '#', '.', '.'},
//                {'.', '#', '.', '#', '.'},
//                {'#', '.', '.', '.', '#'}};
        System.out.println(new Solution().maxStudents(seats));
    }
}

class Solution {
    private Integer[][] f;
    private int n;
    private int[] ss;

    public int maxStudents(char[][] seats) {
        int m = seats.length;
        n = seats[0].length;
        ss = new int[m];
        f = new Integer[1 << n][m];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (seats[i][j] == '.') {
                    ss[i] |= 1 << j;
                }
            }
        }
        return dfs(ss[0], 0);
    }

    private int dfs(int seat, int i) {
        if (f[seat][i] != null) {
            return f[seat][i];
        }
        int ans = 0;
        for (int mask = 0; mask < 1 << n; ++mask) {
            if ((seat | mask) != seat || (mask & (mask << 1)) != 0) {
                continue;
            }
            int cnt = Integer.bitCount(mask);
            if (i == ss.length - 1) {
                ans = Math.max(ans, cnt);
            } else {
                int nxt = ss[i + 1];
                nxt &= ~(mask << 1);
                nxt &= ~(mask >> 1);
                ans = Math.max(ans, cnt + dfs(nxt, i + 1));
            }
        }
        return f[seat][i] = ans;
    }
}
